package com.bupt.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.bupt.datastruct.ArcNode;
import com.bupt.datastruct.Graph;

public class GraphSolution {
	public List<String> DFSTraverse(Graph g){
		List<String> list = new ArrayList<String>();
		boolean[] visited = new boolean[g.vNum];
		for(int i = 0;i < g.vNum;i++) visited[i] = false;
		for(int i = 0;i < g.vNum;i++){
				DFS(g,i,visited,list);
		}
		return list;
	}
	
	public void DFS(Graph g,int i, boolean[] visited,List<String> list){
		if(!visited[i]){
			list.add(g.vNodeList[i].vName);
			visited[i] = true;
			for(ArcNode arc = g.vNodeList[i].firstArc;arc != null; arc = arc.nextArc){
				int w = arc.vNode;
				if(!visited[arc.vNode]){
					DFS(g,w, visited, list);
				}
			}
		}
	}
	
	public List<String> BFSTraverse(Graph g){
		List<String> list = new ArrayList<String>();
		boolean[] visited = new boolean[g.vNum];
		for(int i = 0;i < g.vNum;i++) visited[i] = false;
		LinkedList<Integer> queue = new LinkedList<Integer>();
		for(int i = 0;i < g.vNum;i++){
			if(!visited[i]){
				list.add(g.vNodeList[i].vName);
				visited[i] = true;
				queue.push(i);
				while(!queue.isEmpty()){
					int w = queue.poll();
					for(ArcNode arc = g.vNodeList[w].firstArc;arc != null; arc = arc.nextArc){
						int m = arc.vNode;
						if(!visited[m]){
							list.add(g.vNodeList[m].vName);
							visited[m] = true;
							queue.push(m);
						}
					}
				}
			}
		}
		return list;
	}
}
